[洛谷P1896][SCOI2005]互不侵犯

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

注：数据有加强（2018/4/25）

输入输出格式

输入格式

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式

所得的方案数

输入样例

1
3 2

输出样例

1
16

题解

建议先食用这道题
这道题，其实也是一道模板题，只不过情况稍微复杂了一点，状态稍微难转移一点。

函数\变量名 作用
$f[i][j][m]$ 第$i$行，第$j$个状态，放了$m$个国王
$get_one(x)$ 返回二进制数$x$的1的个数
$can[i]$ 预处理合法状态
$num[i]$ $i$状态有多少个1

和玉米田不同的是，这里$f$的第二维是第$j$个状态而不是状态$j$

预处理$can$以及$f[1]$：
不能有相邻的国王，左移后若没有重叠则合法
顺便将当前状态的第一行赋值为1

后面就和玉米田差不多了，注释里只有与玉米田不同的注释

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
using namespace std;
int n,k,cnt;
long long f[10][1000][100];//第i行，第j个状态，放了m个国王
int can[1000],num[1000];

int get_one(int x){
    int ans=0;
    for(;x>0;x>>=1)ans+=x&1;
    return num[cnt]=ans;
}

int main(){
    cin>>n>>k;
    int top=(1<<n)-1;
    for(int i=0;i<=top;i++){
        if(((i<<1)&i)==0)can[++cnt]=i,f[1][cnt][get_one(i)]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=cnt;j++){
            int x=can[j];
            for(int z=1;z<=cnt;z++){
                int y=can[z];
                if ((x&y)||(x&(y<<1))||(x&(y>>1))) continue;//左下角和右下角都不能放
                for (int l=0;l<=k;l++) f[i][j][num[j]+l]+=f[i-1][z][l];//l是上个状态的国王数量，而我们找到的合法状态国王数量应该是上个国王数量加上当前状态的国王数量
            }
        }
    }
    long long res=0;//注意long long
    for (int i=1;i<=cnt;i++) res+=f[n][i][k];
    printf("%lld",res);
    return 0;
}